//
//  Problem1371.swift
//  TestProject
//
//  Created by 武侠 on 2021/5/18.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 1371. 每个元音包含偶数次的最长子字符串
 给你一个字符串 s ，请你返回满足以下条件的最长子字符串的长度：每个元音字母，即 'a'，'e'，'i'，'o'，'u' ，在子字符串中都恰好出现了偶数次。

 示例 1：
     输入：s = "eleetminicoworoep"
     输出：13
     解释：最长子字符串是 "leetminicowor" ，它包含 e，i，o 各 2 个，以及 0 个 a，u 。
 示例 2：
     输入：s = "leetcodeisgreat"
     输出：5
     解释：最长子字符串是 "leetc" ，其中包含 2 个 e 。
 示例 3：
     输入：s = "bcbcbc"
     输出：6
     解释：这个示例中，字符串 "bcbcbc" 本身就是最长的，因为所有的元音 a，e，i，o，u 都出现了 0 次。
 提示：
     1 <= s.length <= 5 x 10^5
     s 只包含小写英文字母。
 */
@objcMembers class Problem1371: NSObject {
    func solution() {
        print(findTheLongestSubstring("eleetminicoworoep"))
    }
    
    /*
     前缀和
     1: 创建一个状态status，后5位，每一位记录这5个元音的奇偶个数，
        例如 a 3个 e 2个 i 1个 o 2个 u0个
        00101 （uoiea）
     2: 那么所有的状态总共有 00000 ~ 11111 即 0~31
     3: 创建一个数组 slist:[32],存储上面的每一个状态第一次出现的位置, 特例 slist[0] = 0, 即：00000 长度为0也满足需求
     4: 遍历字符串时，更新status每个元音的奇偶数，
     5: 判断status是否在slist中存在，不存在时：它就是第一次出现，直接把位置i放入slist中。存在时：用当前的位置i-slist[status]
     */
    func findTheLongestSubstring(_ s: String) -> Int {
        var result = 0
        
        var status = 0      // 实时统计每个元音
        var slist:[Int] = Array(repeating: -1, count: 32)
        slist[0] = 0        // 所以的元音都是偶数
        
        
        for (i, c) in s.enumerated() {
            if c == "a" {
                status ^= 1 << 0
            } else if c == "e" {
                status ^= 1 << 1
            } else if c == "i" {
                status ^= 1 << 2
            } else if c == "o" {
                status ^= 1 << 3
            } else if c == "u" {
                status ^= 1 << 4
            }
 
            if slist[status] != -1 {
                result = max(result, i + 1 - slist[status])
            } else {
                slist[status] = i + 1
            }
        }
        
        return result
    }
    
    
}
